Nowadays, one-dimensional and two-dimensional bar codes are ubiquitous in the form of so-called “tags”. Specifically, such bar codes can be found on consumer products, electronic and non-electronic devices, machines, vehicles, and also on documents, such as tickets, papers, currency bills etc. Besides the one-dimensional bar code also the two-dimensional bar code has gained in significance during recent years. Whereas the one-dimensional barcode is classically limited to encoding information only in one linear dimension, the two-dimensional bar code, comprising at least first and second type elements arranged in an ordered grid, allows for substantially increasing amount of data amount that can be encoded.
FIGS. 1A and 1B show schematic views of conventional two-dimensional bar codes that encode information by arranging at least first and second type elements, such as rectangles, dots, triangles and the like, for encoding information. At least two distinguishable types of elements are used for encoding information in form of binary units, i.e. bits. For example, a white-printed square as a first type element may represent the information “0”, whereas a black-printed square as a second type element represents the information “1”.
FIG. 1A shows a schematic view of a two-dimensional bar code according to the GS1 (Trademark) DataMatrix ECC 200 standard (GS1 being an international association providing standards for two-dimensional barcodes). This two-dimensional bar code comprises two main areas, namely the so-called “finder pattern” 10 and the data 20. The latter data 20 carries the actual payload data of the bar code and comprises first and second type elements 21, 22 arranged in an ordered grid. The finder pattern 10 is also composed of the first and second type elements, and is, in turn, divided into the so-called “L finder pattern” 11 (also called L-shape solid line, L-line, solid line, etc.) and the so-called “clock track” 12 (also called clock line, L-shape clock line etc.).
According to a convention, the clock line 12 is formed by linearly alternating the arrangement of first and second type elements 21, 22. Therefore, the clock line 12 provides transitions between said first and second type elements 21, 22, whereas the solid line 11 does not. Both segments (or legs) of both the solid line 11 and the clock line 12 intersect at a corner in a substantially perpendicular fashion. Thus, a rectangle-like outline of the two-dimensional barcode is formed by the solid line 11 and the clock line 12.
According to another convention, the intersecting element of the two segments of the clock line 12 is of a pre-determined type, namely either the first type 21 or the second type 22. Specifically, a current convention defines this intersection element 13 as a light element, for example in the context of the present disclosure a first type element, as opposed to dark elements, for example in the context of the present disclosure a second type element.
Whereas FIG. 1A shows a square version of the DataMatrix bar code 1, the current conventions are not limited to square like bar codes and FIG. 1B shows an example of a rectangle implementation 1′. Again, the two-dimensional bar code is delimited by an outline comprising an L-shape solid line 11′ and an L-shape clock line 12′. However, since the general outline is not limited to squares, one segment 111′ of the solid line 11′ may be shorter than the other segment 112′ of the solid line 11′. Correspondingly, one segment 121′ of the clock line 12′ can be shorter than the other segment 122′.
Generally, the first and second type elements 21, 22 may take any distinguishable form. This aspect is depicted in FIG. 2A that shows the first type element 21 as a general right-hatched square/rectangle and the second type element as a general left-hatched square/rectangle 22. This generalization comes from the fact that a two-dimensional bar code is not necessarily printed by using, for example, a black dye on white paper. Rather, the two-dimensional bar code can be well implemented also by color dyes or inks; thermo printing on heat-sensitive paper; mechanically, such as milling, embossing, grinding, etc.; or physically/chemically, such as laser etching, acid etching, etc. Any type of implementation is possible as long as the elements can be distinguished into their respective type in, for example, digital image data that has been obtained from the two-dimensional bar code. For example, a digital camera can obtain digital image data of two-dimensional bar code that is printed on a paper document or laser-etched on a metal can.
Further, the various printing techniques may also result in different “qualities” of a two-dimensional bar code. Besides the somewhat optimal representation (as shown for example in FIGS. 1A and 1B), also implementations with individual elements are possible, such as shown in conjunction with FIG. 2B. There, even the solid line 11 has interruptions between two adjacent elements of the same type 22. However, the average width of such interruptions may still ensure the characteristics of no transition in element type between adjacent elements as shown with reference numeral 28. On the other hand, a transition between the element type can be still identified by the characteristic width of the interruption as shown by reference numeral 29.
FIG. 2C shows a somewhat opposite situation in which even diagonally adjacent elements merge. However, also in this case it is assumed that the first and second type elements can be distinguished and that their respective association to positions in an ordered grid is still possible.
The decoding of a two-dimensional bar code usually begins with taking a photographic image of the two-dimensional barcode on a given item, such as a consumer product or document. This image is then obtained as digital image data defining respective pixel values for the pixels of the image. This digital image data is then subject to image processing by a processing unit (e.g., CPU, computer, server, embedded system, ASIC, etc.). Such processing may be divided into various individual steps for eventually decoding the data that is encoded in the two-dimensional bar code.
Since the image of the two-dimensional bar code is usually taken with an arbitrary perspective, meaning that the precise distance, angle, and general orientation of the imaging device (e.g., a CCD camera) relative to the two-dimensional bar code is unknown. Therefore, it may be necessary to first identify the image or area of the two-dimensional bar code within given digital image data. Once the two-dimensional barcode has been identified in the digital image data, processing may proceed to identifying and decoding the individual elements of the bar code data.
Further, the overall image quality of the input image can be low and there is usually only one single picture taken, so that one has to deal with the low quality input available. The low image quality may stem from the fact that the time available for taking the image is short and that the image needs to be taken in situations in which the item/document, and with it the two-dimensional bar code, moves with considerable speed. For example, a two-dimensional bar code can be attached to an item in a production line (e.g., a beverage can in a filling line) so that many items pass an observation point with high speed and possibly without any halt in its movement that could be used for taking an image. Specifically, it may be the case that only a couple of milliseconds are available to actually take the image.
Still further, the image may contain other features that can be of a similar aspect as that of a two-dimensional bar code. Again with reference to the example of beverage cans, such cans usually carry graphical elements (e.g., manufacturer's logo, symbols, photographs, etc.), text, and even other bar codes (e.g., EAN). As a consequence, the two-dimensional bar code needs not only to be identified from low quality input image date in a fast fashion, but also a decision needs to be made on which features actually correspond to the target two-dimensional bar code.
Generally, initial steps of image processing include the identification of the two-dimensional bar code in the input image data, i.e. a determination on what parts of the input image data comprise the target data to be decoded, and what other parts correspond to “uninteresting” features that need not to be processed further.
Conventional concepts contemplate a sequence of various processing stages that can be, however, too slow for meeting the requirements on a fast decoding/identification. Further, the conventional concepts may not take into account properly the fact that the quality of input image data is low and/or that the input image data comprise other features that may be mistakenly interpreted as a two-dimensional bar code.
Therefore, there is a demand for improving the time efficiency and robustness of existing identification and decoding schemes so that the overall time required from taking an image of two-dimensional bar codes to eventually obtaining the decoded pay load data of the two-dimensional bar code can be minimized, and so that a reliable identification of the actual two-dimensional bar code can be taken, even if the input image data comprises features similar in appearance to a two-dimensional bar code.